package com.lecode.link;

import java.util.ArrayList;
import java.util.List;
import java.util.Stack;

public class Link {
	
	static class ListNode {
		int val;
		ListNode next;
		ListNode(int x) { 
			val = x; 
		}
	}
	
	/**
	 * 合并 k 个排序链表，返回合并后的排序链表。请分析和描述算法的复杂度。
	 * 
	 * 递归：两个两个合并后组成一个新的数组，继续递归合并，直到数组中的节点只剩一个节点返回
	 * @param lists
	 * @return
	 */
	public static ListNode mergeKLists(ListNode[] lists) {
		if(lists.length == 0) return null;
		List<ListNode> list = new ArrayList<ListNode>();
		for(int i = 0; i < lists.length; i++){
			list.add(lists[i]);
		}
		List<ListNode> node = mergeLinkNode(list);
		
		return node.get(0);
	}
	
	public static List<ListNode> mergeLinkNode(List<ListNode> nodes){
		
		if(nodes.size() < 2) return nodes;
		
		List<ListNode> lists = new ArrayList<Link.ListNode>();
		for(int i = 0; i < nodes.size(); i++){
			if(i + 1 < nodes.size()){
				ListNode node = mergeTwoLists(nodes.get(i), nodes.get(i+1));
				lists.add(node);
				i++;
			}else{
				lists.add(nodes.get(i));
			}
		}
		
	    return mergeLinkNode(lists);
	}


	/**
	 * 合并两个链表
	 * @param l1
	 * @param l2
	 * @return
	 */
	public static ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        //始终只想尾节点
        ListNode result = new ListNode(0);
        //头结点
        ListNode head = result;
        
        while(l1 != null && l2 != null){
            if(l1.val < l2.val){
                result.next = l1;
                result = result.next;
                l1 = l1.next;
            }else{
                result.next = l2;
                result = result.next;
                l2 = l2.next;
            }
        }
        if(l1 != null){
            result.next = l1;
        }
        if(l2 != null){
            result.next = l2;
        }
        
        return head.next;
    }
	
	
	/**
	 * 给定一个链表，两两交换其中相邻的节点，并返回交换后的链表
	 * 
	 * 你不能只是单纯的改变节点内部的值，而是需要实际的进行节点交换。
	 * 递归：
	 * 操作的节点：  head、 next、next.next，
	 * 
	 * 
	 * 返回值：交换完成的子链表
	 *	调用单元：设需要交换的两个点为 head 和 next，head 连接后面交换完成的子链表，next 连接 head，完成交换
	 *	终止条件：head 为空指针或者 next 为空指针，也就是当前无节点或者只有一个节点，无法进行交换
	 * 
	 * @param head
	 * @return
	 */
	public static ListNode swapPairs(ListNode head) {
		if(head == null || head.next == null){
			return head;
		}
		
		ListNode next = head.next;
		head.next = swapPairs(next.next);
		next.next = head;
		
		return next;
    }
	
	
	
	/**
	 * 给你一个链表，每 k 个节点一组进行翻转，请你返回翻转后的链表。
	 *k 是一个正整数，它的值小于或等于链表的长度。
	 *
	 *将链表切成k组，对每一组链表使用头插法进行反转
	 *
	 * @param head
	 * @param k
	 * @return
	 */
    public ListNode reverseKGroup(ListNode head, int k) {
    	//始终指向头结点
        ListNode dummp = new ListNode(0);
        dummp.next = head;
        ListNode pre = dummp;
        ListNode start = pre;
        ListNode end = pre;
        
        while(end != null){
        	for(int i = 0; i < k && end != null; i++) end = end.next;
        	if(end == null) break;
        	
        	ListNode next = end.next;
        	end.next = null;
        	start = pre.next;
        	pre.next = reverse(start);
        	pre = start;
        	pre.next = next;
        	end = pre;
        }
    	return dummp.next;
    }

    /**
     * 反转链表
     * 相当于使用头插法将链表进行反转，返回头结点的指针
     * @param start
     * @return
     */
	public ListNode reverse(ListNode start) {
		
		ListNode head = null;
		ListNode curr = start;
		while(curr != null){
			ListNode next = curr.next;
			curr.next = head;
			head = curr;
			curr = next;
		}
		return head;
	}
	
	
	/**
	 * 给定一个链表，旋转链表，将链表每个节点向右移动 k 个位置，其中 k 是非负数。
	 * n链表长度
	 * n - k % n - 1 新链表尾部
	 * 
	 * @param head
	 * @param k
	 * @return
	 */
    public ListNode rotateRight(ListNode head, int k) {
    	// base cases
        if (head == null) return null;
        if (head.next == null) return head;

       
        ListNode old_tail = head;
        int n;
        for(n = 1; old_tail.next != null; n++)
          old_tail = old_tail.next;
        old_tail.next = head;

        ListNode new_tail = head;
        for (int i = 0; i < n - k % n - 1; i++)
          new_tail = new_tail.next;
        ListNode new_head = new_tail.next;

        // break the ring
        new_tail.next = null;

        return new_head;
    }
	
    
	/**
	 * 给定一个排序链表，删除所有含有重复数字的节点。
	 * @param head
	 * @return
	 */
    public static ListNode deleteDuplicates1(ListNode head) {
        if(head == null) return head;
        
        ListNode tail = new ListNode(head.val);
        ListNode next = tail;
        while(head != null){
        	if(head.val != next.val){
        		ListNode temp = head;
        		next.next = temp;
        		head = head.next;
        		temp.next = null;
        		next = temp;
        	}else{
        		head = head.next;
        	}
        }
    	return tail;
    }
    
    
    /**
	 * 给定一个排序链表，删除所有含有重复数字的节点，只保留原始链表中 没有重复出现 的数字。
	 * 
	 * 快慢指针：       
	 * 快指针过滤重复元素
	 * 
	 * @param head
	 * @return
	 */
    public static ListNode deleteDuplicates(ListNode head) {
        if(head == null) return head;
        
        ListNode tail = new ListNode(-1000);
        tail.next = head;
        ListNode slow = tail;
        ListNode fast = tail .next;
        while(fast != null){
        	while(fast.next != null && fast.val == fast.next.val) 
        		fast = fast.next;
        	if(slow.next == fast){
        		slow = fast;
        	}else{
        		slow.next = fast.next;
        	}
        	fast = fast.next;
        }
        return tail.next;
    }
    
    /**
     * 给定一个链表和一个特定值 x，对链表进行分隔，使得所有小于 x 的节点都在大于或等于 x 的节点之前。
	 *	你应当保留两个分区中每个节点的初始相对位置。
     * @param head
     * @param x
     * @return
     */
    public ListNode partition(ListNode head, int x) {
        
    	
    	
    	
    	return null;
    }
    
    public static void main(String[] args) {
		ListNode a = new ListNode(1);
		ListNode b = new ListNode(2);
		ListNode c = new ListNode(2);
		ListNode d = new ListNode(2);
		
		a.next = b;
		b.next = c;
		c.next = d;
		
		ListNode aa = new ListNode(1);
		ListNode bb = new ListNode(3);
		ListNode cc = new ListNode(4);
		
		aa.next = bb;
		bb.next = cc;
		
		ListNode a1 = new ListNode(2);
		ListNode b1 = new ListNode(6);
		
		a1.next = b1;
		
		ListNode[] list = {a, aa, a1};
		
		/*ListNode node = mergeKLists(list);
		while(node != null){
			System.out.println(node.val);
			node = node.next;
		}*/
		
		ListNode node = deleteDuplicates(a);
		while(node != null){
			System.out.println(node.val);
			node = node.next;
		}
	}
    
    
    
    
}
